package leetcode.code034;

public class SearchRange extends Solution034 {

	@Override
	public int[] searchRange(int[] nums, int target) {
		if (nums == null || nums.length == 0)
			return new int[] { -1, -1 };
		int len = nums.length;
		if (target < nums[0] || target > nums[len - 1])
			return new int[] { -1, -1 };
		int lr = -1;
		int rr = -1;
		int l = 0;
		int r = len - 1;
		while (l <= r) {
			int ml = l + ((r - l) >> 1);
			if (target < nums[ml]) {
				r = ml - 1;
			} else if (target > nums[ml]) {
				l = ml + 1;
			} else {
				lr = findlr(nums, l, ml, target);
				rr = findrr(nums, ml, r, target);
				break;
			}
		}
		return new int[] { lr, rr };
	}

	private int findrr(int[] nums, int ml, int r, int target) {
		while (ml <= r) {
			int m = ml + ((r - ml) >> 1);
			if (nums[m] == target) {
				ml = m + 1;
			} else {
				r = m - 1;
			}
		}
		return ml - 1;
	}

	private int findlr(int[] nums, int l, int ml, int target) {
		while (l <= ml) {
			int m = l + ((ml - l) >> 1);
			if (nums[m] == target) {
				ml = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ml + 1;
	}

	public static void main(String[] args) {
		SearchRange sr = new SearchRange();
		sr.debug1();
		sr.debug2();
		sr.debug3();

//		int a = 10;
//		int b = 8;
//		int c = (a-b)>>1;
//		int d = b + ((a-b)>>1) ;
//		System.out.println(c);
//		System.out.println(c + b);
//		System.out.println(d);

	}

}
